package bin_tree.leetcode;

/**
 * @author yuisama
 * @version 1.0.0
 * @Description 将BST转为排序的双向链表
 * 其中链表prev 用 left代替
 * 链表 next 用 right代替
 * @createTime 2023年04月04日 19:41:00
 */
public class Offer36_ConvertTree {
    /**
     * 传入一个以pRoot为根的BST，就能将其转为排序的双向链表，并返回转换后的链表头节点
     * @param pRootOfTree
     * @return
     */
    public TreeNode Convert(TreeNode pRootOfTree) {
        // base case
        if (pRootOfTree == null) {
            return null;
        }
        // 1.先将左子树转为双向链表
        TreeNode head = Convert(pRootOfTree.left);
        // 找到左半链表的尾节点
        TreeNode tail = head;
        while (tail != null) {
            if (tail.right == null) {
                // 此时tail就是尾节点
                break;
            }
            tail = tail.right;
        }
        // 此时tail节点走到了左半链表的尾部
        // 2.将左半链表和根节点拼接
        if (tail != null) {
            // 左子树存在
            tail.right = pRootOfTree;
            pRootOfTree.left = tail;
        }
        // 3.转换右子树和根节点拼接
        TreeNode right = Convert(pRootOfTree.right);
        // 拼接根节点和右半链表
        if (right != null) {
            right.left = pRootOfTree;
            pRootOfTree.right = right;
        }
        return head == null ? pRootOfTree : head;
    }
}
